package bintree.nowcoder;
//JZ36 二叉搜索树与双向链表
//输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

public class Num_JZ36_Convert {
    /**
     * 传入一个树的根节点，就能将这颗 BST树转换为排序的双向链表，并返回头节点
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        //边界
        if(pRootOfTree == null){
            return null;
        }
        //BST根节点的左子树 < 根 < 右子树
        //1.先将左子树转换为排序后的双向链表
        TreeNode leftHead = Convert(pRootOfTree.left);
        //2.找到左子树链表的最后一个节点位置
        TreeNode leftTail = leftHead;
        while(leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        //循环后leftTail就走到了最后节点位置
        //这里需要判断，如果左子树是个空树的话就不需要连接了
        if(leftTail != null){
            //进行连接
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }//连接完毕

        //3.再将右子树转换为双向变量
        TreeNode rightHead = Convert(pRootOfTree.right);
        //连接右子树，只有要 . 操作就需要先判空
        if(rightHead != null){
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }

        //最后然后链表的头节点
        //如果左子树为空的话，链表的头节点是就 根
        return leftHead == null ? pRootOfTree : leftHead;
    }
}
